package 动态规划;

public class No416分割等和子集 {

    /**
     * 给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
     * 注意:
     * 每个数组中的元素不会超过 100
     * 数组的大小不会超过 200
     *
     * 示例 1:
     * 输入: [1, 5, 11, 5]
     * 输出: true
     * 解释: 数组可以分割成 [1, 5, 5] 和 [11].
     * 示例 2:
     * 输入: [1, 2, 3, 5]
     * 输出: false
     * 解释: 数组不能分割成两个元素和相等的子集.
     */

    //前[0..i]个元素 是否 能正好填充[0..j]容量 再写一遍
    public boolean canPartition(int[] nums){

        int sum=0;
        for (int num : nums) {
            sum+=num;
        }
        if(sum%2!=0){
            return false;
        }
        int target=sum/2;
        boolean[][] dp=new boolean[nums.length][target+1];
        //base
//        for (int i = 0; i < nums.length; i++) {
//            //前i个元素是否可以填充满j
//            //!!这里大于target的,一定是不能凑出,但是它前面的不知是否可以凑出,所以这里写错了
//            dp[i][nums[i]]=true;
//        }
        if(nums[0]<=target){
            //为了下面从1开始,不从0开始(因为有i-1麻烦)
            dp[0][nums[0]]=true;
        }

        for (int i = 1; i < nums.length; i++) {
            for (int j = 0; j <= target; j++) {
                if(nums[i]==j){
                    dp[i][j]=true;
                } else if(dp[i-1][j]){
                    dp[i][j]=true;
                }else if(j-nums[i]>0&&dp[i-1][j-nums[i]]){
                    dp[i][j]=true;
                }
            }
        }

        return dp[nums.length-1][target];
    }

    int[] arr;
    Boolean[][] memo=new Boolean[100*201][200];

    public boolean canPartitionDg(int[] nums) {
        int sum=0;
        for (int num : nums) {
            sum+=num;
        }
        if(sum%2!=0){
            return false;
        }
        this.arr=nums;
        return dg(sum/2,0,0);
    }

    private boolean dg(int target,int sum,int index){

        if(index==arr.length||sum>target){
            return false;
        }

        if(target==sum){
            return true;
        }

        if(memo[sum][index]!=null){
            return memo[sum][index];
        }

        boolean flag1=dg(target,sum+arr[index],index+1);
        boolean flag2=dg(target,arr[index],index+1);
        boolean flag3=dg(target,sum,index+1);

        memo[sum][index]=flag1||flag2||flag3;

        return memo[sum][index];
    }


    public static void main(String[] args) {
        No416分割等和子集 n=new No416分割等和子集();
        int[] arr={3,1,2,4};
        boolean result = n.canPartition(arr);
        System.out.println(result);
    }

}
